package algocasts;

public class P78_MinCostClimbingStairs {
    public int minCostClimbingStairs(int[] cost) {
        if (cost == null || cost.length == 0) return 0;
        int n = cost.length;
        if (n == 1) return cost[0];
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++)
            dp[i] = Math.min(dp[i - 2], dp[i - 1]) + cost[i];
        return Math.min(dp[n - 2], dp[n - 1]);
    }

    public int minCostClimbingStairs_O1(int[] cost) {
        if (cost == null || cost.length == 0) return 0;
        if (cost.length == 1) return cost[0];
        int pre2 = cost[0], pre1 = cost[1];
        for (int i = 2; i < cost.length; i++) {
            int cur = Math.min(pre2, pre1) + cost[i];
            pre2 = pre1;
            pre1 = cur;
        }
        return Math.min(pre2, pre1);
    }
}
